#include "calc.h"
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <iterator>
#include <dirent.h>
#include <stdlib.h> // exit()

#include "numrule.h"
#include "number.h"
#include "parser.h"
#include "languageparser.h"
#include "nativeparser.h"

#include "calcexception.h"

/** Declaration of static member fields. */
const string Calc::MSG_OK = "OK";
set<Parser *> Calc::parsers;
map<char, int> Calc::op_precedence;


/** Constructor.
 * Nothing surprising to begin with.
 */
Calc::Calc(string in) 
  : input(in), message(MSG_OK), result(0.0) {}


/** Iterate over parsers. */
Number *Calc::parseNum(string input, size_t &pos) {
  Number *n;
  
  for (set<Parser *>::iterator it = parsers.begin(); it!=parsers.end(); it++) {
    DEBUG("pos " << pos << " " << input.substr(pos));
    DEBUG("parsing num with: " << (*it)->getName());
    Parser *p = *it;
    // Parsers are expected to return NOTANUMBER if string does not match.
    // However, if there is something fishy (e.g. incorrect rules or overflow),
    // an exception must be thrown by the parser. This is checked here. 
    try {
      n = Parser::NOTANUMBER;
      n = p->parseNum(input, pos);
    } catch (exception &e) {
      message = string("PARSE ERROR: ") + e.what();
      return Parser::NOTANUMBER;
    }
    // Parser returns a valid number if and only if:
    // - a number matches
    // - the end of the number can be determined (either explicitly or 
    //   implicitly, e.g. by the appearance of an operator)
    if (n!=Parser::NOTANUMBER) {
      DEBUG("number: " << n->getValue());
      return n;
    }
    DEBUG("parsing num with: " << (*it)->getName() << " failed");
  }
  // If we get this far, n is almost certainly NOTANUMBER. So this check is 
  // somewhat redundant, but safe. This also means that no parser matched a
  // number where there should have been a number.
  if (n==Parser::NOTANUMBER) {
    message = "PARSE ERROR: no parser matched a number";
  }
  
  return Parser::NOTANUMBER;
}

/** Iterate over parsers. */
char Calc::parseOp(string input, size_t &pos) {
  char c = Parser::NOTANOPERATOR;

  for (set<Parser *>::iterator it = parsers.begin(); it!=parsers.end(); it++) {
    DEBUG("pos " << pos << " " << input.substr(pos));
    DEBUG("parsing op with: " << (*it)->getName());
    // Parsers are expected to return NOTANUMBER if string does not match.
    // No exception is expected here, operators are quite straightforward.
    c = (*it)->parseOp(input, pos);
    if (c!=Parser::NOTANOPERATOR) {
      DEBUG("op: " << c);
      return c;
    }
  }
  // See parseNum, above.
  if (c==Parser::NOTANOPERATOR) {
    message = "PARSE ERROR: no parser matched an operator";
  }
  
  return Parser::NOTANOPERATOR;
}

/** The big picture. */
bool Calc::parse() {
  // a running index, expected (but not assumed) to always run forward.
  size_t pos = 0;
  // a stack for storing numbers and operators until another operator is found
  // with same or lower precedence.
  stack<pair<RESULT, char> > st;
  // a local variable for processing. The object is allocated elsewhere, we just
  // need to release it here (except NOTANUMBER, of course)
  Number *n;
  // a local variable for processing.
  char c = Parser::NOTANOPERATOR;

  // ignore whitespace coming. This is not necessary but is useful to provide 
  // a message different from "no parser matched a number".
  while(Parser::WHITESPACE.find(input[pos])!=string::npos) pos++;
  if (pos == input.length()) {      
    message = "input is empty";
    result = 0.0;
    return false;
  }

  // All expressions must start with a number...
  n = parseNum(input, pos);
  // ... followed by zero or more pairs of operator and number.
  while (pos != input.length() && n != Parser::NOTANUMBER) {
    // ignore whitespace coming. Again, this is something that could be done
    // by separate parsers (and parsers should NOT assume that there is no
    // leading whitespace), but helps us dealing with trailing whitespace at the 
    // end of the input.
    while(Parser::WHITESPACE.find(input[pos])!=string::npos) pos++;

    // in case of trailing whitespace the following may happen...
    if (pos == input.length()) {      
      break;
    }

    // So we have parsed at least a number so far, and an operator MUST follow
  DEBUG("parsing op");
    c = parseOp(input, pos);
  DEBUG("parsing op done:" << c);
    if (c == Parser::NOTANOPERATOR) {
      // NO operator found where one should have been. Parse failed.
      // cleanup
      delete n;
      result = 0.0;
      return false;
    }

    // Operator found, check value: it is long, but will be used as RESULT,
    // hence the bigger type.
    RESULT res = n->getValue();
    // n is not needed from this point
    delete n;

    // Apply previous operation, if any, and store current one.
    // There are three cases:
    // 1) the previous operator has same or higher precedence, apply it and
    //    store the new one with the result of previous operation.
    // 2) the previous operator has lower precedence, just store the new one.
    // 3) there is no previous operator, just store the new one.
    while (!st.empty()) {
      pair<RESULT, char> p = st.top();
      int oldprec = op_precedence[p.second];
      int newprec = op_precedence[c];

      if (oldprec < newprec) {
	break;
      }
      // otherwise apply operation and keep going
      RESULT d = p.first;
      // Operations are applied left-to-right
      switch(p.second) {
	case '+': d += res; break;
	case '-': d -= res; break;
	case '*': d *= res; break;
	case '/': d /= res; break;
	default:
	  message = string("Invalid operator: ") + p.second;
	  return false;
      }
      st.pop();
      // store the result of operation instead of the latest number, and check
      // the new top of the stack...
      // Recursion is necessary, e.g. in precedences 1,2,1: the second 1 comes 
      // after 2 and AFTER the first 1. For non-commutative operations (/,-) 
      // this is critical.
      res = d;
    }
    st.push(pair<RESULT, char>(res, c));

    // some debug stuff to keep track of stack contents.
    pair<RESULT, char> p = st.top();
    DEBUG("push: [" << st.size() << "]" << p.first << p.second);

    // Done handling the operator, continue with next number which *MUST* appear
    // (so there is no "trailing whitespace" check here)
    // n was already deleted, safe to recreate
    n = parseNum(input, pos);
  }

  if (n != Parser::NOTANUMBER) {
    // At the end, the result should be calculated by emptying the stack.
    // At this point, the stack should contain operators in strictly increasing 
    // order of precedence (since everything else is processed previously).
    RESULT res = n->getValue();
    // n is not needed from this point
    delete n;

    while (!st.empty()) {
      pair<RESULT, char> p = st.top();

      DEBUG("pop: [" << st.size() << "]" << p.first << p.second);
      RESULT d = p.first;
      // apply from right-to-left (since the all-time result is the right 
      // operand of the previous operation.
      switch(p.second) {
	case '+': res = d+res; break;
	case '-': res = d-res; break;
	case '*': res = d*res; break;
	case '/': res = d/res; break;
	default:
	  message = string("Invalid operator: ") + p.second;
	  return false;
      }
      st.pop();
    }

    // Finally set result and exit successfully.
    result = res;
    message = MSG_OK;
    return true;
  } else {
    // must NOT delete NOTANUMBER
    return false;
  }
}

/** Getter function for message. */
const string Calc::getMessage() {
  return message;
}

/** Loads all parsers into a static map.
 * This is lazily implemented, with no cleanup. This could be a singleton
 * instead. (a great refactoring opportunity if you wish)
 */
void Calc::loadParsers() {
  // MEMORY LEAK HERE!!! unless, of course, you don't run this more than once.
  parsers.clear();

  // Load parsers from files
  // TODO: open `dirname $0` instead
  DIR *dir = opendir("."); 
  if(!dir) { 
    throw CalcException("Error opening directory");
  }

  // Iterate over file names.
  struct dirent *ent; 
  while((ent = readdir(dir)) != NULL) { 
    string s(ent->d_name);
    string parsername;
    // This could be made into something more general as well.
    // E.g. parsers could determine if they are interested in a file or not.
    // That way, not only state machines, but other input files would be 
    // available. A parser factory then could instantiate the parser for that
    // file type.
    //
    // For the time being, we just check for LanguageParser's suffix.
    if (s.length() > LanguageParser::SUFFIX.length() && s.substr(s.length()-LanguageParser::SUFFIX.length()) == LanguageParser::SUFFIX) {
      // debug only. The parser will do just about the same.
      parsername = s.substr(0, s.length()-LanguageParser::SUFFIX.length());
      INFO("Loading parser " << parsername); 
      
      Parser *p = new LanguageParser(s);
      parsers.insert(p);
    }
  } 

  // Create native (numeric) parser
  Parser *p = new NativeParser();
  parsers.insert(p);

  // finally, we load the operator precedence here as well
  op_precedence.insert(pair<char, int>('+',1));
  op_precedence.insert(pair<char, int>('-',1));
  op_precedence.insert(pair<char, int>('*',2));
  op_precedence.insert(pair<char, int>('/',2));
  return;
}

/** Getter function for result. */
const RESULT Calc::getResult() {
  return result;
}
